package com.wtgroup.demo.面试题;

/**
 * 思路一样, 但代码逻辑更简洁
 *
 * 递归里, 两端判断 ?-> 取中 ?-> 选一侧, 递归
 * @author dafei
 * @version 0.1
 * @date 2021/4/5 14:18
 */
public class Q004_无序数组局部最小_S2 {

    public static int m(int[] arr, int left, int right) {
        int n = arr.length;
        if (n==0) {
            return -1;
        }
        if (n == 1 || arr[0] < arr[1]) {
            return 0;
        }
        // here, n>=2
        if (arr[n-1] < arr[n-2]) {
            return n-1;
        }
        // here, 两端非解, and , n>=3, 如果2, 因两数, 且相邻数必不同, 则必定一大一小, 则上面就有结果了.
        // 取中
        int mid = left + ((right - left) >> 1);
        if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
            return mid;
        }

        if (arr[mid - 1] < arr[mid]) {
            // 左侧必有解, 不管右侧了
            return m(arr, left + 1, mid - 1); // left可以+1, mid可以-1
        } else { // here, 必 arr[mid] > arr[mid+1], 取右侧
            return m(arr, mid + 1, right-1); // 里面会判断 mid+1和mid+2关系, mid+1 < mid+2, 返回 mid+1, 这是对的, 因为结合这里的 mid+1 < mid, 即局部最小解
        }
    }
}
